import java.util.Arrays;

/**
 53. 最大子序和
 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 示例:
 输入: [-2,1],
 输出: 6
 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 进阶:
 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 */
public class A624 {
    public static void main(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Solution624 so = new Solution624();
        System.out.println(so.maxSubArray(arr));

    }
}

class Solution624 {
    public int maxSubArray(int[] nums) {
       /* int result = nums[0];
        int sum = nums[0];
        for (int num : nums) {
            if(sum > 0){
                sum += num;
            }else {
                sum = num;
            }
            result = Math.max(result,sum);
        }*/
       int len = nums.length;
       for(int i = 1; i < len;i++){
           if(nums[i - 1] > 0){
               nums[i] += nums[i - 1];
           }
       }
        Arrays.sort(nums);

       return nums[nums.length - 1];











/*        int result = nums[0];
        int sum = 0;
        for (int e : nums) {
            if(sum > 0){
                sum += e;
            }else {
                sum = e;
            }
            result = Math.max(sum,result);
        }
        return result;*/

    }
}
